0% completed
Problem Statement
You are given an integer array asteroids of size n, where asteroids[i] represents the size and direction of the ith asteroid.
The size of an asteroid is represented by the absolute value of asteroids[i], and its direction is indicated by the integer's sign: positive for rightward and negative for leftward. Each asteroid moves at the same speed.
When two asteroids collide, the smaller one shatters. If they are of equal size, both are destroyed. Asteroids moving in the same direction never collide.
Return the final state of asteroids after all possible collisions have been resolved.
Examples
-
Example 1:
- Input: asteroids =
[8, -3, 4, -5] - Expected Output:
[8] - Justification: The asteroid
4collides with-5, and since-5is larger,4is destroyed. Next,-3and-5get destroyed when they collide with 8.
- Input: asteroids =
-
Example 2:
- Input: asteroids =
[-2, -1, 1, 2] - Expected Output:
[-2, -1, 1, 2] - Justification: Since the asteroids are moving in opposite directions, there are no collisions.
- Input: asteroids =
-
Example 3:
- Input: asteroids =
[5, -3, 8, -2, -4, 1, -1] - Expected Output:
[5, 8] - Justification: The sequence of interactions is as follows:
5and-3collide, and-3will get destroyed.8and-2collide, and-2will get destroyed.-4will be destroyed after collision with8.1and-1collide and both are destroyed because they have the same magnitude but opposite directions.- The final configuration is
[5, 8], as these asteroids survive without further collisions.
- Input: asteroids =
Constraints:
- 2 <= asteroids.length <= 104
- -1000 <= asteroids[i] <= 1000
- asteroids[i] != 0
Solution
To solve this problem, we'll use a stack to keep track of the asteroids. This approach works because the problem inherently deals with a sequence of elements where the most recent element might only interact with the one directly before it, which is a perfect scenario for a stack.
When an asteroid moves right (positive), we push it onto the stack. When an asteroid moves left (negative), we compare it with the top of the stack. If the top is moving right, we determine the outcome of the collision. If the asteroid moving left survives, we continue comparing it with the new top of the stack until it either destroys all opposing asteroids or is destroyed itself. This method ensures we only keep asteroids that have survived all possible collisions, effectively simulating the process described in the problem.
Step-by-Step Algorithm
-
Initialize a Stack: Create an empty stack to keep track of the asteroids that are moving or have the potential to cause collisions.
-
Iterate Through Asteroids: Loop through each asteroid in the given array.
- For each asteroid, check if it is moving left (negative value) and if there are any asteroids in the stack moving right (positive value at the top of the stack).
-
Handle Collisions:
- If the current asteroid is moving left and the top of the stack is moving right, a collision might occur. Enter a while loop to handle this potential collision.
- Destroy Bigger Asteroid: Compare the absolute values of the current asteroid and the one at the top of the stack. If the current asteroid is larger, pop the top of the stack (the right-moving asteroid is destroyed), and continue to the next iteration to check for more potential collisions.
- Equal Size Destruction: If the asteroids are of equal size, pop the top of the stack and set the current asteroid to 0 (indicating it has been handled), then break out of the while loop since both asteroids destroy each other.
- Smaller Asteroid Destroyed: If the current asteroid is smaller, simply set it to 0 (indicating it has been handled) and break out of the while loop.
- If the current asteroid is moving left and the top of the stack is moving right, a collision might occur. Enter a while loop to handle this potential collision.
-
Stack Update:
- After handling collisions, if the current asteroid is not set to 0 (indicating it has survived or is moving right without any opposing asteroids), push it onto the stack.
-
Convert Stack to List:
- Once all asteroids have been processed, convert the stack to a list to represent the final state of the asteroid field.
Algorithm Walkthrough
Input: asteroids = [5, -3, 8, -2, -4, 1, -1]
-
Start with an empty stack:
[] -
Process
5:5is moving right, no asteroids to collide with.- Stack after processing
5:[5]
-
Process
-3:-3is moving left and encounters5moving right.- Since
3is smaller than5,-3is destroyed. - Stack remains unchanged:
[5]
-
Process
8:8is moving right, no asteroids to collide with.- Stack after processing
8:[5, 8]
-
Process
-2:-2is moving left and encounters8moving right.- Since
2is smaller than8,-2is destroyed. - Stack remains unchanged:
[5, 8]
-
Process
-4:-4is moving left and encounters8moving right.- Since
4is smaller than8,-4is destroyed. - Stack remains unchanged:
[5, 8]
-
Process
1:1is moving right, no immediate collision as the last asteroid (8) is also moving right.- Stack after processing
1:[5, 8, 1]
-
Process
-1:-1is moving left and encounters1moving right.- Since
-1and1are of equal size, both are destroyed. - Stack after processing
-1(removing1):[5, 8]
-
Final State:
- The final configuration of the asteroid field is represented by the stack:
[5, 8]
- The final configuration of the asteroid field is represented by the stack:
Code
Complexity Analysis
Time Complexity:
The time complexity of this algorithm is
Space Complexity:
The space complexity is
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity:
Space Complexity: